\batchmode
\makeatletter
\def\input@path{{/Users/sergei.winitzki/Code/talks/ftt-fp/}}
\makeatother
\documentclass[english]{beamer}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{secnumdepth}{3}
\setcounter{tocdepth}{3}
\usepackage{babel}
\usepackage{amsmath}
\ifx\hypersetup\undefined
  \AtBeginDocument{%
    \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
  }
\else
  \hypersetup{unicode=true,pdfusetitle,
 bookmarks=true,bookmarksnumbered=false,bookmarksopen=false,
 breaklinks=false,pdfborder={0 0 1},backref=false,colorlinks=true}
\fi

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
% this default might be overridden by plain title style
\newcommand\makebeamertitle{\frame{\maketitle}}%
% (ERT) argument for the TOC
\AtBeginDocument{%
  \let\origtableofcontents=\tableofcontents
  \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
  \def\gobbletableofcontents#1{\origtableofcontents}
}
\newenvironment{lyxcode}
  {\par\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
    \setlength{\listparindent}{0pt}% needed for AMS classes
    \raggedright
    \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
    \normalfont\ttfamily}%
   \def\{{\char`\{}
   \def\}{\char`\}}
   \def\textasciitilde{\char`\~}
   \item[]}
  {\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usetheme[secheader]{Boadilla}
\usecolortheme{seahorse}
\title[Chapter 2: Functional Collections]{Chapter 2: The Functional Approach to Collections}
\author{Sergei Winitzki}
\date{November 22, 2017}
\institute[ABTB]{Academy by the Bay}

\makeatother

\begin{document}
\frame{\titlepage}
\begin{frame}{Tuples}

\begin{itemize}
\item Pair of values: \texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}val a:\ (Int, String) = (123,
``xyz'')}}{\footnotesize\par}
\item Triple of values: \texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}val b:\ (Boolean, Int, Int)
= (true, 3, 4)}}{\footnotesize\par}
\item Tuples can be nested: \texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}val c:\ (Boolean, (String,
Int), Boolean) =}}~\\
\texttt{\textcolor{blue}{\footnotesize{} (true, (``abc'', 3), false)}}{\footnotesize\par}
\item Parts of the tuple can be accessed by number: \texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}val x:\ (String, Int) = c.\_2}}{\footnotesize\par}
\item Functions on tuples:\texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}def f(p:\ (Boolean, Int),
q:\ Int):\ Boolean = p.\_1 \&\& (p.\_2 > q) }}{\footnotesize\par}
\end{itemize}
\end{frame}

\begin{frame}{Pattern-matching syntax for tuples}

Scala allows pattern matching in two places:
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}val }}\textcolor{blue}{\emph{\footnotesize{}pattern}}\texttt{\textcolor{blue}{\footnotesize{}
= ...}} (value assignment)
\item \texttt{\textcolor{blue}{\footnotesize{}case }}\textcolor{blue}{\emph{\footnotesize{}pattern}}\texttt{\textcolor{blue}{\footnotesize{}
}}\textcolor{blue}{\footnotesize{}$\Rightarrow$}\texttt{\textcolor{blue}{\footnotesize{}
...}} (partial function)
\end{itemize}
Examples:
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}val a = (1, 2, 3); val (x,
y, z) = a}}{\footnotesize\par}
\item \texttt{\textcolor{blue}{\footnotesize{}val f:\ ((Int, Int, Int))
$\Rightarrow$ Int = \{ case (x, y, z) $\Rightarrow$ x + y + z \};
f(a)}}{\footnotesize\par}
\end{itemize}
\end{frame}

\begin{frame}{Combining tuple types with other types}

We can use tuple types anywhere:
\begin{itemize}
\item Tuple of functions:\\
 \texttt{\textcolor{blue}{\footnotesize{}val q:\ (Int $\Rightarrow$
Int, Int $\Rightarrow$ Int) = (x $\Rightarrow$ x + 1, x $\Rightarrow$
x - 1)}}{\footnotesize\par}
\item Sequence of tuples:\\
 \texttt{\textcolor{blue}{\footnotesize{}val s:\ Seq{[}(String, Int){]}
=}}~\\
\texttt{\textcolor{blue}{\footnotesize{} \  Seq((``apples'', 3),
(``oranges'', 2), (``pears'', 0))}}{\footnotesize\par}
\item Tuples (esp.\ pairs) are used a lot in the Scala standard library...
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}zip:\ (Seq{[}A{]}, Seq{[}B{]})
$\Rightarrow$ Seq{[}(A, B){]}}}{\footnotesize\par}
\item \texttt{\textcolor{blue}{\footnotesize{}map:\ (Map{[}K, V{]}, (K,
V) $\Rightarrow$ R) $\Rightarrow$ Seq{[}R{]}}}{\footnotesize\par}
\begin{itemize}
\item Note: the syntax \texttt{\textcolor{blue}{\footnotesize{}(a $\rightarrow$
b)}} means the same as the pair \texttt{\textcolor{blue}{\footnotesize{}(a,
b) }}{\footnotesize\par}
\end{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}toMap:\ Seq{[}(K, V){]} $\Rightarrow$
Map{[}K, V{]}}}{\footnotesize\par}
\item \texttt{\textcolor{blue}{\footnotesize{}toSeq:\ Map{[}K, V{]} $\Rightarrow$
Seq{[}(K, V){]}}}{\footnotesize\par}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Worked examples}

\begin{enumerate}
\item for a given sequence $a_{i}$, compute the sequence of pairs $b_{i}=\left(\cos a_{i},\sin a_{i}\right)$
-- use \texttt{\textcolor{blue}{\footnotesize{}.map}}, assume \texttt{\textcolor{blue}{\footnotesize{}a:\ Seq{[}Double{]}}}{\footnotesize\par}
\item in a given sequence $a_{i}$, count how many times $\cos a_{i}>\sin a_{i}$
occurs\\
-- use \texttt{\textcolor{blue}{\footnotesize{}.count}}, assume \texttt{\textcolor{blue}{\footnotesize{}a:\ Seq{[}Double{]}}}{\footnotesize\par}
\item for given sequences $a_{i}$ and $b_{i}$, compute the sequence of
differences\\
 $c_{i}=a_{i}-b_{i}$ (use \texttt{\textcolor{blue}{\footnotesize{}.zip}},
\texttt{\textcolor{blue}{\footnotesize{}.map}}, assume \texttt{\textcolor{blue}{\footnotesize{}a,
b:\ Seq{[}Double{]}}})
\item in a given sequence $a_{i}$, count how many times $a_{i}>a_{i+1}$
occurs
\item for a given $k>0$, compute the sequence $b_{i}=\max(a_{i-k},...,a_{i+k})$\\
 -- use \texttt{\textcolor{blue}{\footnotesize{}.sliding}} 
\item create a multiplication table as a value of type \texttt{\textcolor{blue}{\footnotesize{}Map{[}(Int,
Int), Int{]}}}~\\
 -- use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}}{\footnotesize\par}
\item for a given sequence $a_{i}$, compute the combined set of the numbers
$a_{i}$, $\cos a_{i}$ $\sin a_{i}$ and find its maximum value --
use \texttt{\textcolor{blue}{\footnotesize{}.map, .flatMap, .max}}{\footnotesize\par}
\item from a \texttt{\textcolor{blue}{\footnotesize{}Map{[}String, String{]}}}
mapping names to addresses, and assuming that the addresses do not
repeat, compute a \texttt{\textcolor{blue}{\footnotesize{}Map{[}String,
String{]}}} mapping addresses to names -- use \texttt{\textcolor{blue}{\footnotesize{}.toMap}},
\texttt{\textcolor{blue}{\footnotesize{}.map}}{\footnotesize\par}
\begin{itemize}
\item Write this as a function with type parameters \texttt{\textcolor{blue}{\footnotesize{}Name}}
and \texttt{\textcolor{blue}{\footnotesize{}Address}} instead of the
fixed type \texttt{\textcolor{blue}{\footnotesize{}String}}{\footnotesize\par}
\end{itemize}
\end{enumerate}
\end{frame}

\begin{frame}{Exercises I}

\begin{enumerate}
\item Find all $i,j$ within $\left(0,1,...,9\right)$ such that $i+4*j>i*j$
(use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}})
\begin{itemize}
\item Same task for $i,j,k$ and the condition $i+4*j+9*k>i*j*k$
\end{itemize}
\item Given two sequences \texttt{\textcolor{blue}{\footnotesize{}a:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}String{]}}}
and \texttt{\textcolor{blue}{\footnotesize{}b:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}Boolean{]}}}
of equal length, compute a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}String{]}}}
with those elements of \texttt{\textcolor{blue}{\footnotesize{}a}}
for which the corresponding element of \texttt{\textcolor{blue}{\footnotesize{}b}}
is \texttt{\textcolor{blue}{\footnotesize{}true}} -- use \texttt{\textcolor{blue}{\footnotesize{}.zip}},
\texttt{\textcolor{blue}{\footnotesize{}.map}}, \texttt{\textcolor{blue}{\footnotesize{}.filter}}{\footnotesize\par}
\item Convert a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}Int{]}}} into
a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}(Int, Boolean){]}}}
where the Boolean value is \texttt{\textcolor{blue}{\footnotesize{}true}}
when the element is followed by a larger value; e.g. \texttt{\textcolor{blue}{\footnotesize{}Seq(1,3,2,4)}}
is to be converted into \texttt{\textcolor{blue}{\footnotesize{}Seq((1,true),(3,false),(2,true))}}{\footnotesize\par}
\item Given \texttt{\textcolor{blue}{\footnotesize{}a:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}String{]}}}
and \texttt{\textcolor{blue}{\footnotesize{}b:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}Int{]}}}
of equal length, and assuming that elements of \texttt{\textcolor{blue}{\footnotesize{}b}}
do not repeat, compute a \texttt{\textcolor{blue}{\footnotesize{}Map{[}Int,
String{]}}} that maps numbers from \texttt{\textcolor{blue}{\footnotesize{}b}}
to their corresponding strings from \texttt{\textcolor{blue}{\footnotesize{}a}}{\footnotesize\par}
\begin{itemize}
\item Write this as a function with type parameters \texttt{\textcolor{blue}{\footnotesize{}S}}
and \texttt{\textcolor{blue}{\footnotesize{}I}} instead of the fixed
types \texttt{\textcolor{blue}{\footnotesize{}String}} and \texttt{\textcolor{blue}{\footnotesize{}Int}};
test it with \texttt{\textcolor{blue}{\footnotesize{}S=Boolean}} and
\texttt{\textcolor{blue}{\footnotesize{}I=Set{[}Int{]}}}{\footnotesize\par}
\end{itemize}
\item Given \texttt{\textcolor{blue}{\footnotesize{}a:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}String{]}}}
and \texttt{\textcolor{blue}{\footnotesize{}b:}}~\texttt{\textcolor{blue}{\footnotesize{}Seq{[}Int{]}}}
of equal length, compute a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}String{]}}}
that contains the strings from \texttt{\textcolor{blue}{\footnotesize{}a}}
ordered according to the corresponding numbers from \texttt{\textcolor{blue}{\footnotesize{}b}}
-- use \texttt{\textcolor{blue}{\footnotesize{}.sortBy}}{\footnotesize\par}
\begin{itemize}
\item Write this as a function with type parameter \texttt{\textcolor{blue}{\footnotesize{}S}}
instead of \texttt{\textcolor{blue}{\footnotesize{}String}}{\footnotesize\par}
\end{itemize}
\end{enumerate}
\end{frame}

\begin{frame}{Exercises II}

\begin{enumerate}
\item Given a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}(String, Int){]}}}
showing a list of purchased items (names may repeat), compute \texttt{\textcolor{blue}{\footnotesize{}Map{[}String,
Int{]}}} showing the total counts: e.g.~given a \texttt{\textcolor{blue}{\footnotesize{}Seq((``apple'',
2), (``pear'', 3), (``apple'', 5))}}, compute \texttt{\textcolor{blue}{\footnotesize{}Map(``apple''
$\rightarrow$ 7, ``pear'' $\rightarrow$ 3)}} -- use \texttt{\textcolor{blue}{\footnotesize{}.groupBy}},
\texttt{\textcolor{blue}{\footnotesize{}.map}}, \texttt{\textcolor{blue}{\footnotesize{}.sum}}{\footnotesize\par}
\begin{itemize}
\item Write this as a function with type parameter \texttt{\textcolor{blue}{\footnotesize{}S}}
instead of \texttt{\textcolor{blue}{\footnotesize{}String}}{\footnotesize\par}
\end{itemize}
\item Given a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}List{[}Int{]}{]}}},
compute a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}List{[}Int{]}{]}}}
where each new inner list contains the three largest elements from
the initial inner list -- use \texttt{\textcolor{blue}{\footnotesize{}.sortBy}},
\texttt{\textcolor{blue}{\footnotesize{}.take}}, \texttt{\textcolor{blue}{\footnotesize{}.map}}{\footnotesize\par}
\item Given two sets \texttt{\textcolor{blue}{\footnotesize{}a}}, \texttt{\textcolor{blue}{\footnotesize{}b}}
of type \texttt{\textcolor{blue}{\footnotesize{}Set{[}Int{]}}}, compute
a \texttt{\textcolor{blue}{\footnotesize{}Set{[}(Int, Int){]}}} representing
the Cartesian product of the sets \texttt{\textcolor{blue}{\footnotesize{}a}}
and \texttt{\textcolor{blue}{\footnotesize{}b}} -- use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}}{\footnotesize\par}
\begin{itemize}
\item Write this as a function with type parameters \texttt{\textcolor{blue}{\footnotesize{}I}},
\texttt{\textcolor{blue}{\footnotesize{}J}} instead of \texttt{\textcolor{blue}{\footnotesize{}Int}}{\footnotesize\par}
\end{itemize}
\item {*} Given a \texttt{\textcolor{blue}{\footnotesize{}Seq{[}Map{[}Person,
Amount{]}{]}}}, showing the amounts various people paid on each day,
compute a \texttt{\textcolor{blue}{\footnotesize{}Map{[}Person, Seq{[}Amount{]}{]}}},
showing the sequence of payments for each person (assume \texttt{\textcolor{blue}{\footnotesize{}Person}}
and \texttt{\textcolor{blue}{\footnotesize{}Amount}} are type parameters;
use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}}, \texttt{\textcolor{blue}{\footnotesize{}.toSeq}},
\texttt{\textcolor{blue}{\footnotesize{}.groupBy}})
\end{enumerate}
\end{frame}

\begin{frame}{Mathematical induction I}


\framesubtitle{Computing a number from a sequence}

Typical problem:
\begin{itemize}
\item Compute an integer value from the sequence of its decimal digits
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fromDigits(digits:~Seq{[}Int{]}):~Int~=~???}~\\

\textcolor{blue}{\footnotesize{}fromDigits(Seq(1,~3,~0,~0))~==~1300}{\footnotesize\par}
\end{lyxcode}
Mathematical formulation uses \emph{induction}
\begin{itemize}
\item base case: empty sequence: \texttt{\textcolor{blue}{\footnotesize{}fromDigits(Seq())
= 0}}{\footnotesize\par}
\item induction step: if \texttt{\textcolor{blue}{\footnotesize{}fromDigits}}
is already computed for a sequence \textcolor{blue}{\emph{\footnotesize{}previous}}\textcolor{blue}{\footnotesize{}...},
how to compute it for a sequence with one more element:\texttt{\textcolor{blue}{\footnotesize{}}}~\\
\texttt{\textcolor{blue}{\footnotesize{}fromDigits(Seq(}}\textcolor{blue}{\emph{\footnotesize{}previous...}}\texttt{\textcolor{blue}{\footnotesize{},
x)) = 10 {*} fromDigits(}}\textcolor{blue}{\emph{\footnotesize{}previous...}}\texttt{\textcolor{blue}{\footnotesize{})
+ x}}{\footnotesize\par}
\end{itemize}
Translating mathematical induction into code:
\begin{itemize}
\item use recursion
\item use standard library functions \texttt{\textcolor{blue}{\footnotesize{}fold}},
\texttt{\textcolor{blue}{\footnotesize{}scan}}, etc.
\end{itemize}
\end{frame}

\begin{frame}{Mathematical induction II}


\framesubtitle{Writing a recursive function by hand}
\begin{itemize}
\item base case vs.~inductive step needs to be decided in the code
\item the function calls itself recursively
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fromDigits(digits:~Seq{[}Int{]}):~Int~=}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~if~(digits.isEmpty)~0}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~else~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~val~x~=~digits.last}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~val~rest~=~digits.take(digits.length~-~1)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~~~10~{*}~fromDigits(rest)~+~x}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item lots of code...
\begin{itemize}
\item not very different from writing a loop
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Tail recursion}


\framesubtitle{The ``accumulator'' technique}

The code of \texttt{\textcolor{blue}{\footnotesize{}fromDigits}} calls
itself \emph{in the middle} of an expression:
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fromDigits(...)~=~if~(...)~0}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}else~f(...,~fromDigits(...),~...)}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item The intermediate expression grows, causing expression overflow
\begin{itemize}
\item this crashes our program with a ``stack overflow'' error
\end{itemize}
\item To remedy this: use \textbf{tail recursion} (\texttt{\textcolor{blue}{\footnotesize{}fromDigits}}
is called at the ``tail'')
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}@tailrec~def~fromDigits(...)~=~if~(...)~...~else~\{}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~val~x~=~...}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~fromDigits(...~x~...)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item The ``accumulator technique'' makes \emph{some} functions tail-recursive
\begin{itemize}
\item add another argument that accumulates the final result
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}@tailrec~def~fromDigits(digits:~Seq{[}Int{]},~res:~Int)~=}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~if~(digits.isEmpty)~res}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~else~fromDigits(digits.drop(1),~10~{*}~res~+~digits.head)}{\footnotesize\par}
\end{lyxcode}
\end{itemize}
\end{frame}

\begin{frame}{Mathematical induction III}


\framesubtitle{Computing a number from a sequence}

The library function \texttt{\textcolor{blue}{\footnotesize{}foldLeft}}
implements general induction:
\begin{itemize}
\item base case is the first argument to \texttt{\textcolor{blue}{\footnotesize{}foldLeft}}{\footnotesize\par}
\item induction step is represented by a function \texttt{\textcolor{blue}{\footnotesize{}(previous,
x) $\Rightarrow$ next}}{\footnotesize\par}
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}def~fromDigits(digits:~Seq{[}Int{]}):~Int~=}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}~~digits.foldLeft(0)\{~case~(prev,~x)~$\Rightarrow$~prev~{*}~10~+~x~\}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item see other library functions: \texttt{\textcolor{blue}{\footnotesize{}.foldRight}},
\texttt{\textcolor{blue}{\footnotesize{}.fold}}, \texttt{\textcolor{blue}{\footnotesize{}.reduce}}{\footnotesize\par}
\item most of these functions are tail-recursive
\end{itemize}
\end{frame}

\begin{frame}{Mathematical induction IV}


\framesubtitle{Computing a sequence from a number (\texttt{iterate})}

Typical problem:
\begin{itemize}
\item Compute the sequence of decimal digits of a given integer
\begin{itemize}
\item we cannot solve this with \texttt{\textcolor{blue}{\footnotesize{}.map}},
\texttt{\textcolor{blue}{\footnotesize{}.zip}}, \texttt{\textcolor{blue}{\footnotesize{}.fold}}
etc., because the length of the resulting sequence is unknown
\item we need to ``unfold'' into a sequence of unknown length, and terminate
it when some condition holds
\end{itemize}
\item Inductive definition: given $n>0$, build sequence $(m_{k},d_{k})$
until $(0,0)$:
\begin{align*}
(m_{0},d_{0}) & =(n,0)\\
(m_{k},d_{k}) & =\left(\frac{m_{k-1}}{10},(m_{k-1}\text{ mod }10)\right)\ \text{for}\ k>0
\end{align*}
\end{itemize}
The \texttt{\textcolor{blue}{\footnotesize{}Iterator.iterate }}method
can do this:
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}Iterator.iterate((n,~0))~\{~case~(m,~\_)~\ensuremath{\Rightarrow}~(m~/~10,~m~\%~10)~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}.takeWhile\{case~(m,~d)~\ensuremath{\Rightarrow}~m~>~0~||~d~>~0~\}}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}.drop(1).map(p~=>~p.\_2)~}\textsf{\textcolor{gray}{\footnotesize{}//~extract~the~sequence~of~digits}}{\footnotesize\par}
\end{lyxcode}
\end{frame}

\begin{frame}{Mathematical induction V}


\framesubtitle{Computing a sequence from another sequence (\texttt{scan})}

Typical problem:
\begin{itemize}
\item Compute partial sums of the given sequence: $b_{k}=\sum_{i=0}^{k}a_{i}$
\item Definition by induction:
\begin{align*}
b_{0} & =0\\
b_{k} & =a_{k}+b_{k-1}\ \text{for}\ k>0
\end{align*}
\item Example code:
\end{itemize}
\begin{lyxcode}
\textcolor{blue}{\footnotesize{}val~a~=~Seq(1,~2,~3,~4)}{\footnotesize\par}

\textcolor{blue}{\footnotesize{}val~b~=~a.scan(0)~\{~case~(x,~y)~\ensuremath{\Rightarrow}~x~+~y~\}}\textsf{\textcolor{gray}{\footnotesize{}~//~yields~Seq(0,~1,~3,~6,~10)}}{\footnotesize\par}
\end{lyxcode}
\begin{itemize}
\item \texttt{\textcolor{blue}{\footnotesize{}scanLeft}} implements general
induction:
\begin{itemize}
\item base case is the first argument to \texttt{\textcolor{blue}{\footnotesize{}scanLeft}}{\footnotesize\par}
\item induction step is represented by a function \texttt{\textcolor{blue}{\footnotesize{}(previous,
x) $\Rightarrow$ next}}{\footnotesize\par}
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Summary}

What problems can we solve now?
\begin{itemize}
\item Compute mathematical expressions involving arbitrary recursion
\item Use tail recursion when possible
\item Use arbitrary inductive (i.e.\ recursive) formulas to:
\begin{itemize}
\item convert sequences to numbers (``aggregate'')
\item create new sequences from scratch
\item transform existing sequences 
\end{itemize}
\end{itemize}
What problems are not solved with these tools?
\begin{itemize}
\item Compute non-tail recursive functions without expression overflow
\begin{itemize}
\item The accumulator trick does not always work
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}{Worked examples}

\begin{enumerate}
\item Compute the smallest $n$ such that $f(f(f(...f(1)...)>1000$, where
the function $f$ is applied $n$ times (use \texttt{\textcolor{blue}{\footnotesize{}iterate}}
and test on $f(x)=2x+1$)
\begin{itemize}
\item Write this as a function taking $f$, $1$, and $1000$ as arguments
\end{itemize}
\item Find the $k$-th largest element in an (unsorted) sequence of integers
-- use \texttt{\textcolor{blue}{\footnotesize{}.foldLeft}}{\footnotesize\par}
\item Find the last element of a nonempty sequence -- use pattern matching,
\texttt{\textcolor{blue}{\footnotesize{}.drop}}, and tail recursion
\item Implement binary search over a sorted \texttt{\textcolor{blue}{\footnotesize{}Array{[}Int{]}}}
-- use tail recursion
\item For a given \texttt{\textcolor{blue}{\footnotesize{}n:\ Int}}, compute
the sequence $\left(s_{0},s_{1},s_{2},...\right)$ defined by $s_{0}=SD(n)$
and $s_{k}=SD(s_{k-1})$ for $k>0$, where $SD(p)$ is the sum of
the decimal digits of the integer $p$, e.g. $SD(123)=6$ (use \texttt{\textcolor{blue}{\footnotesize{}iterate}})
\item For a given sequence $\left(s_{0},s_{1},s_{2},...\right)$ of type
\texttt{\textcolor{blue}{\footnotesize{}Iterator{[}T{]}}}, compute
the ``half-speed'' sequence $\left(s_{0},s_{0},s_{1},s_{1},s_{2},s_{2},...\right)$
-- use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}}{\footnotesize\par}
\item Cut off a given sequence $\left(s_{0},s_{1},s_{2},...\right)$ at
a place $k$ where an element $s_{k}$ equals some earlier element
$s_{i}$ with $i<k$ -- use \texttt{\textcolor{blue}{\footnotesize{}.zip}},
\texttt{\textcolor{blue}{\footnotesize{}.takeWhile}}{\footnotesize\par}
\end{enumerate}
\end{frame}

\begin{frame}{Exercises III}

\begin{enumerate}
\item Compute the sum of squared digits of a given integer; e.g., \texttt{\textcolor{blue}{\footnotesize{}dsq(123)=14}}{\footnotesize\par}
\begin{itemize}
\item Same task for an arbitrary function \texttt{\textcolor{blue}{\footnotesize{}f:\ Int$\Rightarrow$Int}}
instead of squaring
\end{itemize}
\item For a given integer $n$, compute the sum of cubed digits, then the
sum of cubed digits of the result, etc.; determine whether the resulting
sequence starts repeating itself, and if so, whether it ever reaches
$1$
\item For a given integer $n$ther it ever reaches
$1$
\item For a given integer $n$, compute the Collatz sequence: $c_{0}=n$
and
\[
c_{k+1}=\begin{cases}
c_{k}/2 & \text{if }c_{k}\text{ is even,}\\
3c_{k}+1 & \text{if }c_{k}\text{ is odd}
\end{cases}
\]

\begin{itemize}
\item Stop the sequence when it reaches $1$
\end{itemize}
\item For \texttt{\textcolor{blue}{\footnotesize{}a,b,c}} of type \texttt{\textcolor{blue}{\footnotesize{}Set{[}Int{]}}},
compute the set of all sets of the form \texttt{\textcolor{blue}{\footnotesize{}Set(x,y,z)}}
where \texttt{\textcolor{blue}{\footnotesize{}x}} is from \texttt{\textcolor{blue}{\footnotesize{}a}},
\texttt{\textcolor{blue}{\footnotesize{}y}} from \texttt{\textcolor{blue}{\footnotesize{}b}},
and \texttt{\textcolor{blue}{\footnotesize{}z}} from \texttt{\textcolor{blue}{\footnotesize{}c}}
(use \texttt{\textcolor{blue}{\footnotesize{}.flatMap}})
\item {*} Same task for a \texttt{\textcolor{blue}{\footnotesize{}Set{[}Set{[}Int{]}{]}}}
instead of just three sets \texttt{\textcolor{blue}{\footnotesize{}a}},\texttt{\textcolor{blue}{\footnotesize{}b}},\texttt{\textcolor{blue}{\footnotesize{}c}}
-- use \texttt{\textcolor{blue}{\footnotesize{}.foldLeft}}{\footnotesize\par}
\end{enumerate}
\end{frame}

\end{document}
